1. Technical Field
This invention relates to information processors, and more particularly to a clustering and association processor for correlating multiple sets of two dimensional data.
2. Discussion
Assignment and correlation problems are among the most difficult to solve using conventional information processors. Assignment problems include those in which a number of entities are to be selected from among many and assigned to other entities in such a way as to force the entire assignment over all entities to be optimal in some sense. In correlation problems, entities in one set of data are correlated with entities in another set of data. These problems are difficult to solve because they are not generally solvable with a single solution but, instead, there may be range of solutions of which the best solution is sought. Moreover, these problems frequently involve a combinatorial explosion, or exponential blowup, in the number of possible answers. Examples of assignment and correlation problems include, among others, resource allocation, object association, two-dimensional position-only track initiation, deghosting for angle only targets detected by multiple sensors, pattern matching of two-dimensional feature vectors, template matching, two-dimensional filtering, computerized tomography, manufacturing inspection vision systems and medical image diagnosis systems.
Previous approaches in this area have emphasized solutions in software on both general purpose and special purpose (vector, array, systolic, etc.) computers. The disadvantage of a software approach is that it requires explicit algorithm and software development and massive computational power. In addition, software solutions are not feasible for application to real-time or near real-time problems. For example, for two-dimensional position-only track initiation problems, estimates for conventional approaches indicate that for a scenario of N objects detected by a sensor, the best conventional algorithms would require on the order of N squared operations. For example, including minimum estimates for memory access and other overhead, with N equal to 100,000, about 10.sup.11 operations per scan would be required. For a ten second scan this equates to 10 billion operations per second, well beyond the realm of conventional solutions.
Another approach to solving these problems is a technique called simulated annealing. See S. Kirkpatrick, Glatt, and Vecchi: "Optimization By Simulated Annealing", 220 Science, p. 671-680 (1983). However, while algorithms using this approach have been developed, to the applicant's knowledge, an actual working architecture has not been implemented. Also, in the image processing domain, systolic and single-planar correlation processors may exist, but are usually limited to in-plane interconnect structures with fixed templates or two-dimensional filtering structures.
One approach to solving assignment problems is to cluster the data into manageable segments. This makes the task of assigning or correlating easier. However, previous approaches to clustering emphasize solutions in software which present the same disadvantages as with solving assignment correlation problems; in particular, the extensive algorithm and software development and slow processing speeds for large amounts of data.
Thus it would be desirable to provide an information processor that can solve clustering and association problems in real time. It would be further desirable to provide a processor capable of solving these problems without extensive algorithm and software development. Also it would be desirable to provide such a processor which can be easily implemented in hardware, while requiring minimum size weight and power.